import java.math.BigInteger;
import java.util.Random;


public class Karatsuba {
	
	public static BigInteger karacuba(BigInteger x, BigInteger y)
	{
		int N = Math.max(x.bitLength(), y.bitLength());
		if (N <= 2000) return x.multiply(y);
		
		N = (N / 2) + (N % 2);
		
		BigInteger b = x.shiftRight(N);
		BigInteger a = x.subtract(b.shiftLeft(N));
		BigInteger d = y.shiftRight(N);
		BigInteger c = y.subtract(d.shiftLeft(N));
		
		BigInteger ac    = karacuba(a, c);
		BigInteger bd    = karacuba(b, d);
		BigInteger abcd  = karacuba(a.add(b), c.add(d));
		
		return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
	}
		 
	public static void main(String[] args)
	{
		Random random = new Random();
		int N = 10;
		BigInteger a = new BigInteger(N, random);
		BigInteger b = new BigInteger(N, random);

		BigInteger c = karacuba(a, b);
		System.out.println("(karatsuba)	" + a.toString() + " * " + b.toString() + " = " + c.toString());
        
		System.out.println();
		
		BigInteger d = a.multiply(b);
		System.out.println("(multiply)	" + a.toString() + " * " + b.toString() + " = " + c.toString());
        
		System.out.println();
		
		System.out.println("Equals: " + c.equals(d));
	}
}